package btree.base.traverse;

import java.util.LinkedList;
import java.util.Queue;

public class BfsTest {

    static class Node {
        int val;
        Node left, right;

        Node(int v) {
            val = v;
        }
    }

    /* 层序遍历（广度优先） */
    static void bfs(Node root, StringBuilder out) {
        if (root == null) return;
        Queue<Node> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            Node cur = q.poll();
            out.append(cur.val).append(' ');
            if (cur.left != null) q.offer(cur.left);
            if (cur.right != null) q.offer(cur.right);
        }
    }

    /* 构造同一棵树并测试
     *        1
     *      /   \
     *     2     3
     *    / \   /
     *   4   5 6
     *
     * 期望层序结果：1 2 3 4 5 6
     */
    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.left = new Node(6);

        StringBuilder sb = new StringBuilder();
        bfs(root, sb);
        String actual = sb.toString().trim();
        String expected = "1 2 3 4 5 6";

        if (!actual.equals(expected)) {
            throw new AssertionError("Expected: " + expected + ", but was: " + actual);
        }
        System.out.println("BFS OK: " + actual);
    }
}
